﻿
Public Class lvlCloser

    Private Class CloserNode
        Public Name As String                   '节点号
        Public Visitted As Boolean              '访问过
        Public LinkCount As Integer             '连接的接点数
        Public IsBM As Boolean                  '是否是起算点
    End Class
    Private Class CloserSide
        Public StartNode As CloserNode
        Public EndNode As CloserNode
        Public Visitted As Boolean
    End Class

    Private closerSides As New List(Of CloserSide)         '所有边
    Private closerNodes As New List(Of CloserNode)         '所有顶点
    Private BHCs As New List(Of String)                    '闭合差集合
    Private mForks As New List(Of String)                  '交叉点
    Private BMPaths As New List(Of String)                 'BM点的全路径


    Sub New(ByRef sLvlLines As List(Of LvlLine), ByVal BMs As List(Of LvlPoint))
        For Each vLine As LvlLine In sLvlLines
            Dim sStart As String = vLine.StartPoint
            Dim sEnd As String = vLine.EndPoint
            Dim StartNode As New CloserNode
            If ExistNode(sStart, StartNode) Then
                StartNode.LinkCount += 1
            Else
                StartNode = AddNode(sStart)
                StartNode.LinkCount = 1
            End If

            Dim EndNode As New CloserNode
            If ExistNode(sEnd, EndNode) Then
                EndNode.LinkCount += 1
            Else
                EndNode = AddNode(sEnd)
                EndNode.LinkCount = 1
            End If

            Dim vSide As New CloserSide
            vSide.StartNode = StartNode
            vSide.EndNode = EndNode
            closerSides.Add(vSide)
        Next

        For Each vBM As LvlPoint In BMs
            For Each vNode As CloserNode In closerNodes
                If vBM.Name = vNode.Name Then
                    'vNode.Level = vBM.Level
                    vNode.IsBM = True
                    Exit For
                End If
            Next
        Next

    End Sub

    Sub New(ByRef Stns As List(Of LvlStation), ByVal BMs As List(Of LvlPoint))
        For Each vStn As LvlStation In Stns
            With vStn
                If .ForePoint.ValidPoint And .BackPoint.ValidPoint Then
                    Dim sStart As String = .BackPoint.Name
                    Dim sEnd As String = .ForePoint.Name
                    Dim StartNode As New CloserNode
                    If ExistNode(sStart, StartNode) Then
                        StartNode.LinkCount += 1
                    Else
                        StartNode = AddNode(sStart)
                        StartNode.LinkCount = 1
                    End If

                    Dim EndNode As New CloserNode
                    If ExistNode(sEnd, EndNode) Then
                        EndNode.LinkCount += 1
                    Else
                        EndNode = AddNode(sEnd)
                        EndNode.LinkCount = 1
                    End If

                    Dim vSide As New CloserSide
                    vSide.StartNode = StartNode
                    vSide.EndNode = EndNode
                    closerSides.Add(vSide)
                End If
            End With
        Next
        For Each vBM As LvlPoint In BMs
            For Each vNode As CloserNode In closerNodes
                If vBM.Name = vNode.Name Then
                    'vNode.Level = vBM.Level
                    vNode.IsBM = True
                    Exit For
                End If
            Next
        Next
    End Sub

    Private Function ExistNode(ByVal Name As String, ByRef vNode As CloserNode) As Boolean
        For Each vN As CloserNode In closerNodes
            If vN.Name = Name Then
                vNode = vN
                Return True
            End If
        Next
        Return False
    End Function
    Private Function AddNode(ByVal Name As String) As CloserNode
        Dim vN As New CloserNode
        vN.Name = Name
        vN.LinkCount = 0
        vN.IsBM = False
        vN.Visitted = False

        closerNodes.Add(vN)
        Return vN
    End Function

    Function SearchCloser(ByVal Treeview1 As TreeView, ByRef Forks As List(Of String)) As List(Of String)
        If closerSides.Count < 1 Then Return Nothing

        'Dim TreeView1 As New TreeView
        '搜索树
        Dim TreeNode As TreeNode = SearchTree()
        Treeview1.Nodes.Add(TreeNode)

        '从访问过的顶点去寻找附合线路
        SearchFHXL(TreeNode)
        '从没访问过的边去寻找闭合线路
        SearchBHXL(TreeNode)

        Forks = mForks

        Return BHCs

        'Dim sTmp As String = String.Empty
        'For Each sL As String In BHCs
        '    sTmp &= sL & vbCrLf
        'Next
        'Return sTmp


    End Function

    '找闭合线路
    Private Sub SearchBHXL(ByRef Tree As TreeNode)

        '从没访问过的边去寻找闭合线路
        For Each vSide As CloserSide In closerSides
            If vSide.Visitted = False Then
                Dim Path1 As String = String.Empty
                Dim Found1 As Boolean = False
                SearchFullPathByName(vSide.StartNode.Name, Tree, Path1, Found1)

                Dim Path2 As String = String.Empty
                Dim Found2 As Boolean = False
                SearchFullPathByName(vSide.EndNode.Name, Tree, Path2, Found2)

                If Found1 And Found2 Then
                    Dim Fork1 As String = String.Empty
                    Dim Fork2 As String = String.Empty
                    AddBHC(Path1, Path2, "BHC", Fork1)

                    For Each vL As String In BMPaths
                        Dim vPnts1() As String = Path1.Split("\")
                        Dim vPnts2() As String = Path2.Split("\")
                        Dim vPntsL() As String = vL.Split("\")

                        FindForkPos(vPnts1, vPntsL, Fork1)
                        FindForkPos(vPnts2, vPntsL, Fork2)
                        If Fork1 = Fork2 Then
                        Else
                            AddFork(Fork1)
                            AddFork(Fork2)
                        End If
                    Next
                End If
            End If
        Next
    End Sub
    Private Sub AddFork(ByVal Fork As String)
        For Each fk In mForks
            If fk = Fork Then
                Exit Sub
            End If
        Next
        mForks.Add(Fork)
    End Sub

    '找附合线路
    Private Sub SearchFHXL(ByRef Tree As TreeNode)
        Dim Bms As New List(Of String)
        For Each vP As CloserNode In closerNodes
            If vP.IsBM Then Bms.Add(vP.Name)
        Next

        For I As Integer = 0 To Bms.Count - 1
            Dim Found As Boolean = False, Path As String = String.Empty
            SearchFullPathByName(Bms(I), Tree, Path, Found)
            If Found Then BMPaths.Add(Path)
        Next

        For I As Integer = 0 To BMPaths.Count - 2
            Dim Path1 As String = BMPaths(I)
            For J As Integer = I + 1 To BMPaths.Count - 1
                Dim Path2 As String = BMPaths(J)
                Dim Fork As String = String.Empty
                AddBHC(Path1, Path2, "FHC", Fork)

                '岔点不是水准点的话，且为新的岔点的话，加入岔点集合
                Dim ForkIsNotBM As Boolean = True
                For Each vP As String In Bms
                    If vP = Fork Then
                        ForkIsNotBM = False
                        Exit For
                    End If
                Next
                If ForkIsNotBM Then AddFork(Fork)
            Next
        Next
    End Sub

    Private Sub AddBHC(ByVal Path1 As String, ByVal Path2 As String, ByVal Type As String, ByRef Fork As String)
        Dim vPnts1() As String = Path1.Split("\")
        Dim vPnts2() As String = Path2.Split("\")
        Dim ForkPos As Integer = FindForkPos(vPnts1, vPnts2, Fork)

        Dim BHC As String = String.Empty
        For I As Integer = vPnts1.Length - 1 To ForkPos Step -1
            BHC &= vPnts1(I) & "→"
        Next
        For I As Integer = ForkPos + 1 To vPnts2.Length - 1
            BHC &= vPnts2(I) & "→"
        Next

        If Type = "BHC" Then
            BHC &= vPnts1(vPnts1.Length - 1)
        ElseIf Type = "FHC" Then
            BHC = Mid(BHC, 1, BHC.Length - 1)
        End If

        BHCs.Add(BHC)
    End Sub
    Private Function FindForkPos(ByRef vPnts1 As String(), ByRef vPnts2 As String(), ByRef Fork As String) As Integer
        Dim LastSameIndex As Integer = 0
        For I As Integer = 0 To Math.Min(vPnts1.Length - 1, vPnts2.Length - 1)
            If vPnts1(I) = vPnts2(I) Then
                LastSameIndex = I
            Else
                Exit For
            End If
        Next
        Fork = vPnts1(LastSameIndex)
        FindForkPos = LastSameIndex
    End Function

    '在树中查找点号
    Private Sub SearchFullPathByName(ByVal Name As String, ByRef Tree As TreeNode, ByRef FullPath As String, ByRef Found As Boolean)

        '找指定树节点，若符合则Found
        If Tree.Text = Name Then
            FullPath = Tree.FullPath
            Found = True
        Else
            '指定树节点不符合，遍历树的子节点，进入递归搜索
            If Tree.Nodes.Count > 0 Then
                For Each Node As TreeNode In Tree.Nodes
                    SearchFullPathByName(Name, Node, FullPath, Found)
                    If Found Then Exit For
                Next
            End If
        End If
    End Sub

    ''' <summary>
    ''' 包括全部结点的树的搜索
    ''' </summary>
    ''' <remarks></remarks>
    Private Function SearchTree() As TreeNode
        ''找连通点最多的固定点
        Dim MaxLinkNodeBMIndex As Integer = SearchMaxLinkBMNode()

        Dim myTree As New TreeNode
        With closerNodes(MaxLinkNodeBMIndex)
            myTree.Text = .Name
            .Visitted = True
            FoundChild(myTree)
        End With

        Return myTree
    End Function
    Private Sub FoundChild(ByRef myTree As TreeNode)
        Dim CurrentNodeName As String = myTree.Text
        Dim HaveAddChild As Boolean = False
        '找当前节点的子节点
        For Each vSide As CloserSide In closerSides
            '遍历每条边
            '对已访问过的边不处理，否则继续
            If vSide.Visitted = False Then
                '对未访问过的边，检测是否与当前节点相关
                '边的两个端点有一端点与当前点Name相同，则相关
                Dim NodeText As String = String.Empty
                Dim LinkSide As Boolean = False
                If vSide.StartNode.Name = CurrentNodeName Then
                    NodeText = vSide.EndNode.Name
                    LinkSide = True
                ElseIf vSide.EndNode.Name = CurrentNodeName Then
                    NodeText = vSide.StartNode.Name
                    LinkSide = True
                End If
                '若相关，则检测另一端点是否已被访问过
                If LinkSide Then
                    Dim vNode As CloserNode = FoundNodeByName(NodeText)
                    If Not vNode Is Nothing Then
                        '找到另一节点
                        '若已被访问过则此条边为多余观测()
                        '否则新增一个树节点，并将节点设置为visitted
                        If vNode.Visitted Then
                            '端点已被访问过，此条边为多余观测；下一步用来生成闭合环，此时不用
                        Else
                            '若端点没访问过，则找到了新的子节点，在当前节点上增加子节点
                            Dim ChildNode As New TreeNode
                            ChildNode.Text = NodeText
                            vSide.Visitted = True
                            vNode.Visitted = True
                            myTree.Nodes.Add(ChildNode)
                            HaveAddChild = True
                        End If
                    End If
                End If
            End If
        Next

        '若增加过子节点，则为子节点搜索"孙"节点,进行递归运行
        If HaveAddChild Then
            For Each mChild As TreeNode In myTree.Nodes
                FoundChild(mChild)
            Next
        End If
    End Sub
    Private Function FoundNodeByName(ByVal Name As String) As CloserNode
        For Each vNode As CloserNode In closerNodes
            If vNode.Name = Name Then
                Return vNode
                Exit For
            End If
        Next
        Return Nothing
    End Function

    ''' <summary>
    ''' 找连接边最多的固定点，返回其序号
    ''' </summary>
    ''' <returns></returns>
    ''' <remarks></remarks>
    Private Function SearchMaxLinkBMNode() As Integer
        Dim MaxLinkIndex As Integer = 0
        Dim MaxLinkCount As Integer = 0
        For I As Integer = 0 To closerNodes.Count - 1
            With closerNodes(I)
                If .IsBM Then
                    If .LinkCount > MaxLinkCount Then
                        MaxLinkCount = .LinkCount
                        MaxLinkIndex = I
                    End If
                End If
            End With
        Next
        Return MaxLinkIndex
    End Function

End Class
